HCF of 2 Numbers Using Euclid Lemma


 
 
Concept Explanation
 

HCF of 2 Numbers Using Euclid Lemma

Euclid Division Algorithm to Find HCF:

It is a technique which helps us to speed up the process of computing the highest common factor. It is based on the fact

  a = bq + r

Then HCF(a,b) = HCF (b,r)

                         = HCF (b, (a-bq)

Example: Find the HCF of 75 and 35

HCF( 75,35)= HCF( 35, (75- 2 X 35))

                    = HCF( 35, 5)

                    = HCF ( 5, (35 -7X 5))

                    = HCF (5,0)=5

 The Euclidean algorithm ( also called Euclid s division algorithm) can be described as follows:

TO obtain HCF of two integers a and b with a > b > 0 we follow the following steps:

Step I   If b=0, then HCF (a,b) = a.

           If b > 0, find integers q and r such that

           a = bq + r where 0<  r < b.

Step II  Replace a by b and b by r and go back to Step I.

Example 1    Use Euclid s division algorithm to find HCF of 196 and 3820.

Solution       Here a = 3820  and  b = 196

Step I        3820 = 196 X 19 + 96

large therefore                   q = 19 and r = 96

Step II    Set a = 196    and b = 96

              Go back to Step 1.

Step III    196 = 96 X 2 + 4 where   q = 2 and r = 4

Step IV     Set a = 96    and b = 4

               Perform Step step I.

Step I     96 = 24 X 4 + 0

              large therefore   q = 24   and   r =0

Step II  Now as r = 0 So HCF = 4

Thus, HCF ( 3820, 196) = 4

 
Video Link - Have a look !!!
 
Language - English
 
 
 
Related Videos
Language - English


Students / Parents Reviews [20]